package i_SegmentTree;

public class SegmentTree<E> {

    private E[] tree;
    private E[] data;
    private Merger<E> merger;

    public SegmentTree(E[] arr, Merger<E> merger){

        this.merger = merger;

        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++)
            data[i] = arr[i];

        tree = (E[])new Object[4 * arr.length];
        buildSegmentTree(0, 0, arr.length - 1);
    }

    // 在treeIndex的位置创建表示区间[l...r]的线段树
    private void buildSegmentTree(int treeIndex, int l, int r){  //使用递归 而不是dp，即自顶向下。所以要用区间来作递归参数，构建树肯定要赋值，所以treeIndex也要有；

        if(l == r){
            tree[treeIndex] = data[l];  //对应值记在对应的treeIndex里 就不需要返回值来给上层递归传值了，根据堆的思想是可以随时取到的；
            return;
        }

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        int mid = l + (r - l) / 2; 	// int mid = (l + r) / 2;
        buildSegmentTree(leftTreeIndex, l, mid); //第一次递归
        buildSegmentTree(rightTreeIndex, mid + 1, r);	//*第一次递归进去后，下边的递归们，其实都是挂件。因为递归的层次是递归参数来决定的，后边的递归会跟着第一次递归层层深入，当停下来(返回到最底的有效层)时，后边的递归们才会执行，使用的是当前层次的递归参数；

        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }

    public int getSize(){
        return data.length;
    }

    public E get(int index){
        if(index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is illegal.");
        return data[index];
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return 2*index + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return 2*index + 2;
    }

    //* 返回区间[queryL, queryR]的值
    public E query(int queryL, int queryR){

        if(queryL < 0 || queryL >= data.length ||
                queryR < 0 || queryR >= data.length || queryL > queryR)	//保证一定能找到
            throw new IllegalArgumentException("Index is illegal.");

        return query(0, 0, data.length - 1, queryL, queryR);
    }

    // 在以treeIndex为根的线段树中[l...r]的范围里，搜索区间[queryL...queryR]的值
    private E query(int treeIndex, int l, int r, int queryL, int queryR){

        if(l == queryL && r == queryR)   //递归是可以多路递归的，所以递归终止条件是多路统一的，对于每一个递归终止条件都应该是啥？这样思考就能想通了。
            return tree[treeIndex];						//如果分多路，每一路都有自己明确的目标；
        
        int mid = l + (r - l) / 2;                   //递归驱动；无处理逻辑，仅将最底层处理逻辑的结果 折返返回
        // treeIndex的节点分为[l...mid]和[mid+1...r]两部分
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if(queryL >= mid + 1)
            return query(rightTreeIndex, mid + 1, r, queryL, queryR);
        else if(queryR <= mid)
            return query(leftTreeIndex, l, mid, queryL, queryR);
        else {
        	 E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
             E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);	//程序虽串行，但结果仍是并行的结果；每一层都二路，越底层越多路；
             return merger.merge(leftResult, rightResult);
        }
       
    }

    //* 将index位置的值，更新为e
    public void set(int index, E e){

        if(index < 0 || index >= data.length)		//不论是query还是set 都先保证了 一定找的到，这样就不会递归到null了，即merge函数不需要担心参数为null的情况；
            throw new IllegalArgumentException("Index is illegal");

        data[index] = e;
        set(0, 0, data.length - 1, index, e);
    }
    
    //	这个递归已经可以隔几天后脑补出来了；
    /*
     * 
     * 是否递归？一个递归单元是什么样的？ *递归的状态变量是谁？* 需不需要给上层传值(可以先假设不需要)？            ————确认参数和语意；
     * 递归宏观是什么样子展开的？ *多路吗？* 每一路都应该符合的终止条件是啥？回到倒数第二层要传值吗？				————终止条件；                                                           
	 * （每一层的递归 要执行什么操作吗？）																（————处理逻辑；）   
	 * 每一层想开始递归时要分哪几种情况吗？ 每一种情况里，还要分路递归吗？如果分路(根据语意分路)，要对各路结果进行merge吗？      			————开始递归；    				
	 * 						 ps：分路递归时，非首次递归在首次递归的每一层里都是挂件，都是跟随当前递归参数来执行；首次递归完全返回后，紧随其后的递归就成为了首次递归；
	 */
    // 在以treeIndex为根的线段树中更新index的值为e
    private void set(int treeIndex, int l, int r, int index, E e){

        if(l == r){
            tree[treeIndex] = e;
            return;
        }

        int mid = l + (r - l) / 2;
        // treeIndex的节点分为[l...mid]和[mid+1...r]两部分

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if(index >= mid + 1)
            set(rightTreeIndex, mid + 1, r, index, e);
        else // index <= mid
            set(leftTreeIndex, l, mid, index, e);

        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);//不论是query还是set 都先保证了 一定找的到，这样就不会递归到null了，即merge函数不需要担心参数为null的情况；
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append('[');
        for(int i = 0 ; i < tree.length ; i ++){
            if(tree[i] != null)
                res.append(tree[i]);
            else
                res.append("null");

            if(i != tree.length - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }
}
